package com.felix.algorithms.tree;

import lombok.ToString;

import java.util.*;

/**
 * ConvertSortedArrayToBinarySearchTree
 *
 * @author xuejinhua
 * @date 2018/9/26 11:27
 */
@ToString
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }
}

/**
 * Merge Two Binary Trees
 */
class Solution617{
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        TreeNode newRoot = calValue(t1, t2);
        commonElementTraversal(t1, t2, newRoot);
        return newRoot;
    }

    private void commonElementTraversal(TreeNode t1, TreeNode t2, TreeNode newRoot) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(t1);
        queue.add(t2);
        queue.add(newRoot);
        while (!queue.isEmpty()) {
            t1 = queue.poll();
            t2 = queue.poll();
            newRoot = queue.poll();
            newRoot.left = calValue(t1.left, t2.left);
            newRoot.right = calValue(t1.right, t2.right);
            if (t1.left != null && t2.left != null) {
                queue.add(t1.left);
                queue.add(t2.left);
                queue.add(newRoot.left);
            }
            if (t1.right != null && t2.right != null) {
                queue.add(t1.right);
                queue.add(t2.right);
                queue.add(newRoot.right);
            }
        }
    }

    private TreeNode calValue(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        return new TreeNode(t1.val + t2.val);
    }
}
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }


    private static TreeNode createBinaryTreeByArray(Integer[] array, int index) {
        if (index >= array.length) {
            return null;
        }
        Integer value = array[index];
        if (value == null) {
            return null;
        }
        TreeNode root = new TreeNode(value);
        root.left = createBinaryTreeByArray(array, 2 * index + 1);
        root.right = createBinaryTreeByArray(array, 2 * index + 2);
        return root;
    }

    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack1 = new Stack<>();
        stack1.push(root1);
        while (!stack1.isEmpty()) {
            root1 = stack1.pop();
            if (root1.left != null) stack1.push(root1.left);
            if (root1.right != null) stack1.push(root1.right);
            if (root1.left == null && root1.right == null) {
                list.add(root1.val);
            }
        }
        Stack<TreeNode> stack2 = new Stack<>();
        stack2.push(root2);
        int index = 0;
        while (!stack2.isEmpty()) {
            root2 = stack2.pop();
            if (root2.left != null) stack2.push(root2.left);
            if (root2.right != null) stack2.push(root2.right);
            if (root2.left == null && root2.right == null) {
                if (list.get(index) != root2.val) return false;
                index++;
            }
        }
        return index == list.size();
    }

    public static TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L) {
            return trimBST(root.right, L, R);
        }
        if (root.val > R) {
            return trimBST(root.left, L, R);
        }
        if (root.val <= R && root.val >= L) {
            root.right = trimBST(root.right, L, R);
            root.left = trimBST(root.left, L, R);
        }
        return root;
    }

    public static TreeNode trimBst(TreeNode root, int L, int R) {
        if (root == null) return null;
        while (root.val > R || root.val < L) {
            if (root.val > R) {
                root = root.left;
            }
            if (root.val < L) {
                root = root.right;
            }
        }
        TreeNode temp = root;
        while (temp != null) {
            while (temp.left != null && temp.left.val < L) {
                temp.left = temp.left.right;
            }
            temp = temp.left;
        }
        temp = root;
        while (temp != null) {
            while (temp.right != null && temp.right.val < R) {
                temp.right = temp.right.left;
            }
            temp = temp.right;
        }
        return root;
    }

    public static boolean isValidBST(TreeNode root) {
        //初始的时候，对根节点没有范围要求
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public static boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        //检查是否满足根节点的范围要求//
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        //修改对子节点的要求，对于左子树，本节点的值就是最大值，对于右子树，本节点的值就是最小值
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }

    public static void main(String[] args) {
        Integer[] arr1 = {8,4,10,2,12,null,20};
        TreeNode root = createBinaryTreeByArray(arr1, 0);
        System.out.println(isValidBST(root));
    }
}